When software programming was in its early stages, a software application was commonly created as one large binary file. In other words, the result of compiling a software application was a single executable file. Software developers quickly learned that this method produced inefficiencies because many different applications included large portions of fundamentally identical code. From that issue evolved dynamic linking. With dynamic linking, a software application is written in two or more pieces. The code in one piece may refer to code in another piece. When the application is compiled, a separate component of binary code is created for each piece of the application. When the application is launched, the pieces are linked together in memory to form the entire application.
Dynamic linking allows common pieces of code to be reused extensively. Code that is routinely used in different applications is brought together into a single library and removed from those applications. Multiple applications may be written that each refer to the same library. A copy of the compiled library is linked in memory to each of the multiple applications only when they are executed. The result is that the code is more easily reused, and is more maintainable. For the purpose of this discussion, each separate body of compiled code is termed a “component” regardless of whether it is a portion of an application, a system service or utility, a library, or any other executable binary. Common examples of executable binaries applicable to the Microsoft Windows operating system are those identified as “EXE,”“DLL,” and “SYS” type files. In addition, the term “application,” as used herein, means a group of components that act in conjunction to achieve some function. In this document, the term “application” includes operating system functions as well as add-on programs.
Although dynamic linking has many advantages, it is not without disadvantages as well. For instance, today software is so complex that it is common to have multiple levels of references. In other words, one component may refer to a second component, the second component may refer to a third component, and so on. As software evolves, some code may be moved from one library to another. Over time, undesirable references can occur, such as circular referencing. Circular referencing refers to the situation where multiple components reference each other in a circular link. For example, one component may refer to a second component, and the second component may refer back to the first component. Circular links often route through multiple components before coming back to the first. If multiple libraries become circularly linked, then for all practical purposes the entire group is effectively a single binary because none of the individual components can safely be used without all the others. This has a negative impact on the modularity of each component. For this reason, discovering when these circular references occurs would be highly advantageous.
In addition, making changes to a linked component must be done with caution. To ensure that a change to one component will not cause problems with any other existing component, the developer must be able to accurately identify the entire list of components that refer to the changed component. For the purpose of this discussion, the terms “dependant” and “dependency” are used to described the relationship between components that refer to other components. A first component that refers to code in a second component is said to “depend” on the second component. The “dependencies” of the second component include the first component.
When analyzing software, it is often necessary to determine the entire list of dependencies for each component associated with an application. This is the only way to determine the entire footprint of the application. When determining how much storage space is necessary to contain an application, the full dependency tree of the application must be determined. The “full dependency tree” means the entire list of components that depend, either directly or indirectly, on a particular component. Determining the full dependency tree of a component or application can be extremely difficult or time consuming using conventional mechanisms.
Accordingly, although mechanisms exist that are capable of finding a full dependency tree, the existing mechanisms are very time-consuming and provide relatively little information compared to the invention.